package q779_kthGrammar;

public class Solution_2 {
    /*
    注意到规律：每一行的后半部分正好为前半部分的“翻转”:
    前半部分是 0 后半部分变为 1，前半部分是 1，后半部分变为 0。
    且每一行的前半部分和上一行相同。我们可以通过「数学归纳法」来进行证明。
    有了这个性质，那么我们再次思考原问题：
    对于查询某一个行第 k 个数字，如果 k 在后半部分，
    那么原问题就可以转化为求解该行前半部分的对应位置的“翻转”数字，
    又因为该行前半部分与上一行相同，所以又转化为上一行对应对应的“翻转”数字。
    那么按照这样一直递归下去，并在第一行时返回数字 0 即可。
     */
    public int kthGrammar(int n, int k) {
        if (k == 1) {
            return 0;
        }
        if (k > (1 << (n - 2))) {
            return 1 ^ kthGrammar(n - 1, k - (1 << (n - 2)));
        }
        return kthGrammar(n - 1, k);
    }
}
